package com.xy6.jvm.fork.test;

import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;

/**
 * a demo of a ForkJoin sort that sorts a given {@code long[]} array
 * 
 * @author dell
 * @since 2018-01-01
 */
public class SortSubTask extends RecursiveAction {

	private static final long serialVersionUID = 8675668298202308664L;

	private static int THRESHOLD = 3;

	private long[] array;

	private int low;

	private int high;

	SortSubTask(long[] array, int low, int high) {
		this.array = array;
		this.low = low;
		this.high = high;
	}

	@Override
	protected void compute() {
		if (high - low <= THRESHOLD) {
			sequentiallySort(array, low, high);
			System.out.println(String.format("sort: %d, %d: %s", low, high, Arrays.toString(array)));
		} else {
			int middle = (low + high) >>> 1;
			invokeAll(new SortSubTask(array, low, middle), new SortSubTask(array, middle + 1, high));
			merge(array, low, high);
		}
	}

	/**
	 * 对数组中一个子数组进行顺序排列，采用选择排序
	 * 
	 * @param array
	 * @param low
	 * @param high
	 */
	private void sequentiallySort(long[] array, int low, int high) {
		long temp = 0;
		for (int i = low; i <= high; i++) {
			long min = array[i];
			int flag = i;
			for (int j = i + 1; j <= high; j++) {
				if (array[j] < min) {
					min = array[j];
					flag = j;
				}
			}
			if (flag == i) {
				continue;
			}
			temp = array[i];
			array[i] = array[flag];
			array[flag] = temp;
		}
	}

	/**
	 * 合并两个有序序列，分界点为(low + high) >>> 1
	 * 
	 * <pre>
	 * 归并排序的合并阶段。时间复杂度为(high-low+1)*2
	 * </pre>
	 * 
	 * @param array
	 * @param low
	 * @param high
	 */
	private void merge(long[] array, int low, int high) {
		int middle = (low + high) >>> 1;
		long[] a = new long[high - low + 1];
		int idx = 0;
		int leftIdx = low;
		int rightIdx = middle + 1;
		while (leftIdx <= middle && rightIdx <= high) {
			if (array[leftIdx] <= array[rightIdx]) {
				a[idx++] = array[leftIdx++];
			} else {
				a[idx++] = array[rightIdx++];
			}
		}
		for (int i = leftIdx; i <= middle; i++) {
			a[idx++] = array[i];
		}
		for (int i = rightIdx; i <= high; i++) {
			a[idx++] = array[i];
		}
		for (int i = low; i <= high; i++) {
			array[i] = a[i - low];
		}
		a = null;
		System.out.println(String.format("merge: %d, %d: %s", low, high, Arrays.toString(array)));
	}

	public final static ForkJoinPool mainPool = new ForkJoinPool();

	public static void main(String[] args) {
		int n = 10;
		long[] a = new long[n];
		Random r = new Random();
		for (int i = 0; i < n; i++) {
			a[i] = r.nextInt(100);
		}
		SortSubTask task = new SortSubTask(a, 0, n - 1);
		mainPool.invoke(task);
		System.out.println(Arrays.toString(a));
	}

}
